1. Technical Field
This invention relates to the field of processing commands to a resource, and in particular to systems and methods for rearranging the order in which commands to a resource are processed.
2. Related Art
Modem computer systems include a variety of devices that are coupled through one or more buses to access different resources in the computer system. For example, a computer system may include a central processing unit (CPU), a graphics system, and peripheral devices, each of which may access a resource such as main memory. In order to minimize latencies, commands from a device initiating an access to the resource must be transferred and implemented as efficiently as possible. The speed with which commands are transferred between a resource and initiating device is governed largely by the intervening buses and the arbitration scheme employed in the computer system. The speed with which commands are implemented at the resource is determined by the nature of the resource and, in many cases, by the order in which the resource processes commands from the initiating device. The faster the resource implements commands, the sooner the device can continue its operations and the sooner the resource can be made available to other devices.
The dependence of resource efficiency on command order may be understood with reference to storage resources such as random access memories ("RAMs"), hard and floppy discs, compact discs (CD) ROMs, digitial video discs (DVDs) and the like. Each of these storage resources is a two dimensional array of addressable data storage locations, with each location specified by two parameters, e.g. row/column, track/sector, page/column, etc. Communicating each parameter to the storage device and activating the associated row, column, track, sector, page, etc., contributes a time delay or overhead to the access. To the extent that storage locations can be accessed without updating both parameters, access times for the resource can be reduced and the resource made to operate more efficiently. Paged memories and other memory architectures are designed to do just this. For example, a memory operating in page mode can access a range of addresses (columns) on the same (open) page without incurring the delay associated with updating the page parameter.
Certain storage resources, e.g. DRAMs, are also characterized by a cycle time, which represents the time necessary to precharge the resource between accesses. The cycle time limits the speed with which consecutive accesses can be made to a DRAM. Interleaved memories are organized into groups of DRAMs or memory banks to minimize overhead due to cycle times. Blocks of contiguous data are mapped to different memory banks (interleaving), and data blocks are retrieved by overlapping accesses to different memory banks. This reduces the impact of each DRAM's cycle time on the data access time and allows the resource to operate more efficiently.
By storing a data block with the appropriate addressing scheme, paging, interleaving, and other strategies allow a command targeting the data block to be implemented with reduced latency. However, these benefits extend across command boundaries only when contiguous commands to the resource happen to access data that falls in the sequence prescribed by the memory organization. In effect, paging, interleaving, and like strategies enhance efficient resource operation with respect to the data targeted by a given command, but do not provide any mechanism to extend these efficiencies across multiple commands. Such a mechanism requires reordering commands sent to the resource according to the state of the resource.
Command reordering has been implemented in a few specific cases. For example, some processors can reorder instructions to eliminate data dependencies and avoid pipeline stalls attributable to unavailable resources. However, this reordering occurs within the processor and does not implicate the efficiency with which resources outside the processor are used. Some chipsets implement "lazy writes", which wait for a read hit to an address before implementing a pending write to the same address. However, this is a passive technique which does not actively reorder commands within a command stream.
There is thus a need for a system that reorders commands to a resource in a manner that allows the resource to operate more efficiently and reduce the latency with which commands to the resource are implemented.